//给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的
//根节点的引用。
//
// 一般来说，删除节点可分为两个步骤：
//
//
// 首先找到需要删除的节点；
// 如果找到了，删除它。
//
//
//
//
// 示例 Array.prototype.unshift:
//
//
//
//
//输入：root = [5,3,6,2,4,null,7], key = 3
//输出：[5,4,6,2,null,null,7]
//解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
//一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
//另一个正确答案是 [5,2,6,null,4,null,7]。
//
//
//
//
// 示例 2:
//
//
//输入: root = [5,3,6,2,4,null,7], key = 0
//输出: [5,3,6,2,4,null,7]
//解释: 二叉树不包含值为 0 的节点
//
//
// 示例 3:
//
//
//输入: root = [], key = 0
//输出: []
//
//
//
// 提示:
//
//
// 节点数的范围 [0, 10⁴].
// -10⁵ <= Node.val <= 10⁵
// 节点值唯一
// root 是合法的二叉搜索树
// -10⁵ <= key <= 10⁵
//
//
//
//
// 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
//
// Related Topics 二叉树 二叉搜索树 二叉树 👍 1100 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/*
找到此节点：
Array.prototype.unshift.如果为叶子，直接删除
2.如果有右有左，右根跑到这个位置上，左根跑到右根的最左（或者左根跑这位置，右根跑左根右边）
3.如果只有右或左 则右或左跑到这个位置就行
 */
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    function removeTargetNode(root: TreeNode): TreeNode | null {
        if (root.left === null && root.right === null) return null;
        if (root.right === null) return root.left;
        if (root.left === null) return root.right;
        let curNode: TreeNode | null = root.right;
        while (curNode.left !== null) {
            curNode = curNode.left;
        }
        curNode.left = root.left;
        return root.right;
    }
    let preNode: TreeNode | null = null,
        curNode: TreeNode | null = root;
    while (curNode !== null) {
        if (curNode.val === key) break;
        preNode = curNode;
        if (curNode.val > key) {
            curNode = curNode.left;
        } else {
            curNode = curNode.right;
        }
    }
    if (curNode === null) return root;
    if (preNode === null) {
        // 删除头节点
        return removeTargetNode(curNode);
    }
    if (preNode.val > key) {
        preNode.left = removeTargetNode(curNode);
    } else {
        preNode.right = removeTargetNode(curNode);
    }
    return root;
};
//leetcode submit region end(Prohibit modification and deletion)
